/*
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？*/
class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    /*
    dp[i][j]表示走到坐标i,j中有dp[i][j]种不同的路径
    初始化第一行为1，因为只能从左向右走
    第一列为1，因为只能从上往下走
    当i!=0,j!=0 dp[i][j]=dp[i-1][j]+dp[i][j-1]
    返回dp数组中右下角的值
    */
    int uniquePaths(int m, int n) {
        // write code here
        int dp[101][101];
        int i,j;
        for(i=0;i<m;i++)
            dp[i][0]=1;
        for(j=0;j<n;j++)
            dp[0][j]=1;
        for(i=1;i<m;i++)
            for(j=1;j<n;j++)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
        return dp[m-1][n-1];
    }
};